package com.leetcode;


//这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
//
// 给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 kⁿ 种方式），使得骰子面朝上的数字总和等于 target。
//
// 由于答案可能很大，你需要对 10⁹ + 7 取模。
//
//
//
// 示例 1：
//
//
//输入：n = 1, k = 6, target = 3
//输出：1
//解释：你掷了一个有 6 个面的骰子。
//得到总和为 3 的结果的方式只有一种。
//
//
// 示例 2：
//
//
//输入：n = 2, k = 6, target = 7
//输出：6
//解释：你掷了两个骰子，每个骰子有 6 个面。
//有 6 种方式得到总和为 7 的结果: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1。
//
//
// 示例 3：
//
//
//输入：n = 30, k = 30, target = 500
//输出：222616187
//解释：返回的结果必须对 10⁹ + 7 取模。
//
//
//
// 提示：
//
//
// 1 <= n, k <= 30
// 1 <= target <= 1000
//
//
// Related Topics 动态规划 👍 312 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

//leetcode submit region end(Prohibit modification and deletion)

public class No1155 {
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[target + 1][n + 1];
        for (int i = 1; i <= target; i++) {
            for (int j = 1; j <= n; j++) {
                for (int l = 1; l <= k; l++) {
                    if (i < l) {
                        continue;
                    }
                    if (j == 1) {
                        if (i == l) {
                            dp[i][j] = 1;
                        }
                    } else {
                        dp[i][j] = (dp[i][j] + dp[i - l][j - 1]) % 1000000007;
                    }
                }
            }
        }
        return dp[target][n];
    }
}
